/*
 *https://leetcode.cn/problems/longest-palindromic-subsequence/description/
 *516. 最长回文子序列
 *medium 吴朝泽 2024.10.15
 *区间DP
*/

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size(); 
        int f[n][n]; // 用于存储子字符串的最长回文子序列的长度
        memset(f, 0, sizeof(f)); 

        // 将对角线上的元素设置为 1，因为单个字符本身是回文的
        for (int i = 0; i < n; ++i) 
            f[i][i] = 1; 
        // 从后向前遍历字符串，i 表示子串的起始位置
        for (int i = n - 1; ~i; --i) 
        {
            // j 从 i + 1 开始，表示子串的结束位置
            for (int j = i + 1; j < n; ++j) 
            {
                // 当 s[i] 和 s[j] 相等时，可以构成回文
                if (s[i] == s[j]) 
                    f[i][j] = f[i + 1][j - 1] + 2; // 包含 s[i] 和 s[j] 的回文子序列长度
                else 
                    // 否则，取去掉 s[i] 或去掉 s[j] 的最长回文子序列
                    f[i][j] = max(f[i + 1][j], f[i][j - 1]);
            }
        }
        return f[0][n - 1];
    }
};
